Extension tables store the calls and answers for a predicate. If a call has been made before, answers are retrieved from the extension table instead of being recomputed. Extension tables provide a caching mechanism for Prolog. In addition, extension tables affect the termination characteristics of recursive programs. Some Prolog programs, which are logically correct, enter an infinite loop due to recursive predicates. An extension table saved on recursive predicates can find all answers (provided the set of such answers is finite) and terminate for some logic programs for which Prolog's evaluation strategy enters an infinite loop. Iterations over the extension table execution strategy provides complete evaluation of queries over function-free Horn clause programs.
To be able to use the simple extension table evaluation on a set of predicates, the source file should either be consulted, or compiled with the t option (the t option keeps the assembler from optimizing subroutine linkage and allows the extension table facility to intercept calls to predicates).
To use extension table execution, all predicates that are to be saved in the extension table must be passed to et/1. For example,
The predicate noet/1 takes a list of predicate/arity pairs for which ET-points should be deleted. Notice that once an ET-point has been set up for a predicate, it will be maintained unless explicitly deleted via noet/1. If the definition of a predicate which has an ET-point defined is to be updated, the ET-point must first be deleted via noet/1. The predicate can then be reloaded and a new ET-point established. This is enforced by the failure of the goal ``et(P/N)'' if an ET-point already exists for the argument predicate. In this case, the following error message will be displayed:
There are, in fact, two extension table algorithms: a simple one, which simply caches calls to predicates which have ET-points defined; and a complete ET algorithm, which iterates the simple extension table algorithm until no more answers can be found. The simple algorithm is more efficient than the complete one; however, the simple algorithm is not complete for certain especially nasty forms of mutual recursion, while the complete algorithm is. To use the simple extension table algorithm, predicates can simply be called as usual. The complete extension table algorithm may be used via the query
The extension table algorithm is intended for predicates that are ``essentially pure'', and results are not guaranteed for code using impure code. The extension table algorithm saves only those answers which are not instances of what is already in the table, and uses these answers if the current call is an instance of a call already made. For example, if a call p(X, Y), with X and Y uninstantiated, is encountered and inserted into the extension table, then a subsequent call p(X, b) will be computed using the answers for p(X, Y) already in the extension table. Notice that this might not work if var/nonvar tests are used on the second argument in the evaluation of p.
Another problem with using impure code is that if an ET predicate is cut over, then the saved call implies that all answers for that predicate were computed, but there are only partial results in the ET because of the cut. So on a subsequent call the incomplete extension table answers are used when all answers are expected. An example is shown in Figure 11
Let p be an ET predicate whose evaluation yields many tuples. In the evaluation of the query, r(X,Y) makes a call to p(X,Y). Assuming that there is a tuple such that q(Y,Z) succeeds with the first p tuple then the evaluation of p is cut over. The call to p(X,Y) in the query uses the extension table because of the previous call in the evaluation of r(X,Y). Only one answer is found, whereas the relation p contains many tuples, so the computation is not complete. Note that ``cuts'' used within the evaluation of an ET predicate are ok, as long as they don't cut over the evaluation of another ET predicate. The evaluation of the predicate that uses cuts does not cut over any ET processing (such as storing or retrieving answers) so that the tuples that are computed are saved. In the following example, the ET is used to generate prime numbers where an ET point is put on prime/1. Example:
prime(I) :- globalset(globalgenint(2)),fail. /* Generating Primes */
prime(I) :- genint(I), not(div(I)).
div(I) :- prime(X), 0 is I mod X.
genint(N) :-
repeat,
globalgenint(N),
N1 is N+1,
globalset(globalgenint(N1)).
The following summarizes the library predicates supporting the extension table facility:
L must be instantiated at the time of the call to noet/1.
All extension tables can be emptied by using et_points/1 in conjunction with et_remove/1.